package com.java.hashtable;

import java.util.UUID;

/**
 * @author 19252
 * @date 2020/7/21
 */
public class HashTableDemo {
    public static void main(String[] args) {

        MyHashTable hashTable = new MyHashTable(7);
        int length = 100;
        Employee employee;
        for (int i = 0; i < length; i++) {
            employee = new Employee(i, UUID.randomUUID().toString());
            hashTable.addEmployee(employee);
        }
        hashTable.showHashTable();
        System.out.println("查询验证！");
        System.out.println(hashTable.findEmployee(77));
        System.out.println(hashTable.findEmployee(100));
    }
}

/**
 * 创建 hashTable 管理多个链表
 */
class MyHashTable {

    /**
     * 链表数组用于生成多个链表
     */
    private EmployeeLinkedList[] employeeLinkedListArray;

    /**
     * 指定hashTable的容量
     */
    private int size;

    /**
     * 初始化 hashTable
     * @param size 指定 hashTable的大小
     */
    public MyHashTable(int size) {
        this.size = size;
        employeeLinkedListArray = new EmployeeLinkedList[size];
        // 初始化 employeeLinkedListArray，要不然它其中的每个元素都是null
        for (int i = 0; i < size; i++) {
            employeeLinkedListArray[i] = new EmployeeLinkedList();
        }
    }

    public EmployeeLinkedList[] getEmployeeLinkedListArray() {
        return employeeLinkedListArray;
    }

    public void setEmployeeLinkedListArray(EmployeeLinkedList[] employeeLinkedListArray) {
        this.employeeLinkedListArray = employeeLinkedListArray;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    /**
     * 编写散列函数，散列函数有很多种写法
     * 在这里就使用简单取模的方法即可
     * @return 返回 id 与 size 取模后的结果，就是这个员工应该放在哪个链表
     */
    public int hashFunction(int id){
        return id % size;
    }

    /**
     * 向 hashTable 中添加员工
     * @param employee 要添加的员工
     */
    public void addEmployee(Employee employee){
        int id = hashFunction(employee.getId());
        // 获取到取模结果后，根据结果放入hashTable中
        employeeLinkedListArray[id].addEmployee(employee);
    }

    /**
     * 在 hashTable 中查找员工
     * @param id 员工id
     * @return 查找到返回员工对象，否则返回 null
     */
    public Employee findEmployee(int id){
        return employeeLinkedListArray[hashFunction(id)].findEmployee(id);
    }

    /**
     * 遍历hashTable (就是遍历所有的链表)
     */
    public void showHashTable(){
        for (int i = 0; i < size; i++) {
            System.out.printf("展示第 %d 条链表 \n", i);
            employeeLinkedListArray[i].showLinkedList();
        }
    }

}

/**
 * 表示员工
 */
class Employee {

    /**
     * 员工 id
     */
    private int id;
    /**
     * 员工姓名
     */
    private String name;
    /**
     * 指向下一个节点的指针
     */
    private Employee next;

    public Employee() {

    }

    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Employee getNext() {
        return next;
    }

    public void setNext(Employee next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

/**
 * 建立员工链表
 */
class EmployeeLinkedList {

    /**
     * 链表的头结点 默认为空
     */
    private Employee head = new Employee();

    public Employee getHead() {
        return head;
    }

    public void setHead(Employee head) {
        this.head = head;
    }

    /**
     * 向链表添加员工
     * 先默认添加到链表的最末尾
     */
    public void addEmployee(Employee employee){
        Employee temp = head;
        while (temp.getNext() != null){
            temp = temp.getNext();
        }
        temp.setNext(employee);
    }

    public Employee findEmployee(int id){
        Employee temp = head;
        if (temp.getNext() == null){
            System.out.println("查无此人！");
            return null;
        }
        while (temp.getNext() != null){
            if (temp.getNext().getId() == id){
                return temp.getNext();
            }
            temp = temp.getNext();
        }
        System.out.println("查无此人！");
        return null;
    }

    /**
     * 遍历链表
     */
    public void showLinkedList(){
        Employee temp = head;
        if (temp.getNext() == null){
            System.out.println("链表为空！");
            return;
        }
        while (temp.getNext() != null){
            System.out.println(temp.getNext());
            temp = temp.getNext();
        }
    }
}